package com.sh.redis.suanfa;

public class ShangLouTi {


    public static void main(String[] args) {
        System.out.println(dpOrder(10));
    }


    static int dpOrder(int n){
        int result = 0;
        int[] dp = new int[n+1];
        result = dp1(n, dp);
        return result;
    }

    static int dp1(int i, int[] dp){
        if(i<=2){
            dp[i] = i;
            return i;
        }else{
            if(dp[i] == 0){
                dp[i] = dp1(i-1, dp)+ dp1(i-2, dp);
            }else{
                return dp[i];
            }
        }
        return dp[i];
    }



    static int dpOrder2(int n){
        int result = 0;
        int f = 0;
        int l = 0;
        result = dp1(n);
        return result;
    }

    static int dp1(int i){
        int f = 0;
        int l = 0;
        if(i<=2){
            return i;
        }else{
            for(int m=2; m<i; m++){
                f = dp1(m-2);
                l = dp1(m-1);
            }
        }
        return 1;
    }
}


